package com.usts.edu.graphic;

import com.usts.edu.Queue.LinkQueue;

/**
 * Created by Guanzhong Hu
 * Date :2020/3/30
 * Description :
 * Version :1.0
 */
public class GDSeach {
        public final static int INFINITY = Integer.MAX_VALUE;

        public static void CC_BFS(IGraph G) throws Exception {
            boolean[] visited = new boolean[G.getVexNum()];
            for (int v = 0; v < G.getVexNum(); v++)

                visited[v] = false;
            LinkQueue Q = new LinkQueue();
            LinkQueue P = new LinkQueue();
            int i = 0;
            for (int v = 0; v < G.getVexNum(); v++) {
                P.clear();
                if (!visited[v]) {
                    visited[v] = true;
                    P.offer(G.getVex(v));
                    Q.offer(v);
                    while (!Q.isEmpty()) {
                        int u = (Integer) Q.poll();
                        for (int w = G.firstAdjVex(u); w >= 0; w = G.nextAdjVex(u,
                                w)) {
                            if (!visited[w]) {
                                visited[w] = true;
                                P.offer(G.getVex(w));
                                Q.offer(w);
                            }
                        }
                    }
                    System.out.println("图的第" + ++i + "个连通分量为：");
                    while (!P.isEmpty())
                        System.out.print(P.poll().toString() + " ");
                    System.out.println();
                }
            }
        }

        public static void main(String[] args) throws Exception {
            Object vexs[] = { "A", "B", "C", "D", "E", "F", "G" };
            int[][] arcs = { { 0, 1, INFINITY, 1, INFINITY, INFINITY, INFINITY },
                    { 1, 0, 1, INFINITY, INFINITY, INFINITY, INFINITY },
                    { INFINITY, 1, 0, 1, INFINITY, INFINITY, INFINITY },
                    { 1, INFINITY, 1, 0, INFINITY, INFINITY, INFINITY },
                    { INFINITY, INFINITY, INFINITY, INFINITY, 0, 1, INFINITY },
                    { INFINITY, INFINITY, INFINITY, INFINITY, 1, 0, 1 },
                    { INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, 1, 0 }, };
            MGraph G = new MGraph(GraphKind.UDG, 7, 6, vexs, arcs);
            CC_BFS(G);
        }
}
